/* file: cg_image.cc */

#include "cg_image.h"

extern map<string, int> table;	// map IP address to its prior

/**********************************
class:	CGImage
constructor
**********************************/
CGImage::CGImage()
{
    tree.clear();
    ip = "";
    level = 0;
    root = "";
    depth = 0;
    pthread_mutex_init(&lock, NULL);
}

CGImage::CGImage(string ip, int level, string root, int depth)
{
    tree.clear();
    this->ip = ip;
    this->level = level;
    this->root = root;
    this->depth = depth;
    pthread_mutex_init(&lock, NULL);
}

/**********************************
class:	CGImage
method:	setFather
param:	ip
set current node's father
**********************************/
void
CGImage::setFather(const string &ip)
{
    vector<node>::iterator node_it;

    node_it = tree[this->ip].begin();
    while (node_it != tree[this->ip].end())
    {
	if (node_it->level == this->level) break;
	++node_it;
    }
    node_it->father = ip;
    this->father = ip;
}

/**********************************
class:	CGImage
method:	loadCGImage
param:	filename
return:	0 if success
	-1 if error
**********************************/
int
CGImage::loadCGImage(char *filename)
{
    FILE *fp;			// file_descriptor of config_file
    char str[20], str2[20];
    int real_node;
    int i, j, k;
    struct node p;
    vector<node>::size_type ni;
    
    /* open the config_file */
    if ((fp = fopen(filename, "r")) == NULL)
    {
	perror("fopen() error ");
	return -1;
    }
    
    /* load the config information */
    fscanf(fp, "%s", str);
    this->ip = str;
    fscanf(fp, "%d %d", &real_node, &depth);
    for (i = 1; i <= real_node; i++)
    {
	fflush(fp);
	fscanf(fp, "%s %d", str, &k);
	table[str] = k;
    }
    fflush(fp);
    while (fscanf(fp, "%s", str) > 0)
    {
	fscanf(fp, "%d %d ", &j, &k);
	if (j == 0)
	{
	    root = str;
	    p.state = ONLINE;
	    p.father = "0.0.0.0";
	    p.level = 0;
	    p.group.clear();
	    tree[str].push_back(p);
	}
	
	for (i = 1; i <= k; i++)
	{
	    for (ni = 0; ni != tree[str].size(); ++ni)
	    {
		if (tree[str][ni].level == j) break;
	    }
	    /*node_it = tree[str].begin();
	    while (node_it != tree[str].end())
	    {
		if (node_it->level == j) break;
		++node_it;
	    }
	    if (node_it == tree[str].end())*/
	    if (ni == tree[str].size())
	    {
		printf("config file error\n");
		return -1;
	    }
	    
	    fscanf(fp, "%s", str2);
	    tree[str][ni].group.push_back(str2);
	    p.state = ONLINE;
	    p.father = str;
	    p.level = j+1;
	    tree[str2].push_back(p);
	}
	fflush(fp);
    }
#ifdef DEBUG
    printf("loadCGImage complete\n");
#endif
    
    if (fclose(fp) < 0)
    {
	perror("fclose() error ");
	exit(1);
    }

    return 0;
}

/**********************************
class:	CGImage
method:	initPosition
param:	ip, level, depth
**********************************/
void
CGImage::initPosition(const string &ip, int level, string root, int depth)
{
    this->ip = ip;
    this->level = level;
    this->root = root;
    this->depth = depth;
}

/**********************************
class:	CGImage
method:	printCGMap
**********************************/
void
CGImage::printCGMap()
{
    map<string, vector<node> >::iterator map_it;
    vector<node>::size_type ni;
    vector<string>::size_type si;

    pthread_mutex_lock(&lock);
    printf("***** CGMap *****\n");
    map_it = tree.begin();
    while (map_it != tree.end())
    {
	printf("%s %d\n", map_it->first.c_str(), map_it->second.size());
	for (ni = 0; ni != map_it->second.size(); ++ni)
	{
	    printf("\t(%d)[%d] father:%s group:", map_it->second[ni].level, map_it->second[ni].state, map_it->second[ni].father.c_str());
	    for (si = 0; si != map_it->second[ni].group.size(); ++si)
	    {
		printf("%s ", map_it->second[ni].group[si].c_str());
	    }
	    printf("\n");
	}
	++map_it;
    }
    pthread_mutex_unlock(&lock);
}

/**********************************
class:	CGImage
method:	printCGTree
**********************************/
void
CGImage::printCGTree()
{
    char str[BUFF_MAXSIZE] = "";
    pthread_mutex_lock(&lock);
    printf("***** Level %d sub_tree *****\n", this->level);
    printSubTree(ip, level, str);
    pthread_mutex_unlock(&lock);
}

/**********************************
class:	CGImage
method:	printSubTree
**********************************/
void
CGImage::printSubTree(string sub_ip, int sub_level, char *str)
{
    vector<node>::size_type ni, mi;
    vector<string>::size_type si;
    int i, len, tag;
    string child;

    for (ni = 0; ni != tree[sub_ip].size(); ++ni)
	if (tree[sub_ip][ni].level == sub_level) break;
    if (tree[sub_ip][ni].state == ONLINE)
    {
	// print this branch_root
	printf("%s(%d)\n", sub_ip.c_str(), sub_level);
    }
    else return;

    if (sub_level > 0)
    {
	len = strlen(str);
	for (i = 1; i < 8; ++i) str[len-i] = ' ';
    }
    strcat(str, "|-------");
    len = strlen(str);
  
    tag = tree[sub_ip][ni].group.size();
    if ((tag = tree[sub_ip][ni].group.size()) > 0)
    {
	for (si = tag-1; si >= 0; --si)
	{
	    child = tree[sub_ip][ni].group[si];
	    for (mi = 0; mi != tree[child].size(); ++mi)
		if (tree[child][mi].level == sub_level+1) break;
	    if (mi != tree[child].size() && tree[child][mi].state == ONLINE)
	    {
		tag = si;
		break;
	    }
	}
    }
    
    for (si = 0; si != tree[sub_ip][ni].group.size(); ++si)
    {
	child = tree[sub_ip][ni].group[si];
	for (mi = 0; mi != tree[child].size(); ++mi)
	    if (tree[child][mi].level == sub_level+1) break;
	if (mi != tree[child].size() && tree[child][mi].state == ONLINE)
	{
	    printf("%s", str);
	    if (si == tag) str[len-8] = ' ';
	    printSubTree(tree[sub_ip][ni].group[si], sub_level+1, str);
	}
    }
    str[len-8] = '\0';
    len = strlen(str);
    if (sub_level > 0)
    {
	for (i = 1; i < 8; ++i) str[len-i] = '-';
	//str[len-8] = '|';
    }
}

/**********************************
class:	CGImage
method:	codeCGImage
param:	ip, level, *str
**********************************/
int
CGImage::codeCGImage(string ip, int level, char *str)
{
    vector<node>::size_type ni;
    struct in_addr naddr;
    int offset;
  
    pthread_mutex_lock(&lock);
    for (ni = 0; ni != tree[ip].size(); ++ni)
    {
	if (tree[ip][ni].level == level) break;
    }
    if (ni == tree[ip].size())
    {
#ifdef DEBUG
	printf("sub_tree not exist\n");
#endif
	pthread_mutex_unlock(&lock);
	str[0] = '\0';
	return 0;
    }
    
    // current node's father
    inet_aton(tree[ip][ni].father.c_str(), &naddr);
    if ((offset = sprintf(&str[0], "%u ", naddr)) < 0) perror("sprintf() error ");
    offset = codeSubImage(ip, level, str, offset);
    pthread_mutex_unlock(&lock);
    
    return offset;
}

/**********************************
class:	CGImage
method: codeSubImage
param:	sub_ip, sub_level, str, offset
return:	next byte in str
**********************************/
int
CGImage::codeSubImage(string sub_ip, int sub_level, char *str, int offset)
{
    vector<node>::iterator node_it;
    vector<node>::size_type ni;
    vector<string>::size_type ix;
    struct in_addr naddr;
    int len, num;
    string ip;

    node_it = tree[sub_ip].begin();
    for (node_it = tree[sub_ip].begin(); node_it != tree[sub_ip].end(); ++node_it)
    {
	if (node_it->level == sub_level) break;
    }
    if (node_it == tree[sub_ip].end())
    {
#ifdef DEBUG1
	printf("subtree not exist\n");
#endif
	return offset;
    }
    if (node_it->state != ONLINE) return offset;	// subtree offline

    if ((len = sprintf(&str[offset], "(")) < 0) perror("sprintf() error ");
    offset += len;
    
    inet_aton(sub_ip.c_str(), &naddr);
    //naddr = inet_addr(sub_ip.c_str());
    //printf("%s %u\n", sub_ip.c_str(), naddr);
    if ((len = sprintf(&str[offset], " %u %u ", naddr, sub_level)) < 0) perror("sprintf() error ");
    offset += len;

    // count online children number
    num = 0;
    for (ix = 0; ix < node_it->group.size(); ++ix)
    {
	for (ni = 0; ni < tree[node_it->group[ix]].size(); ++ni)
	    if (tree[node_it->group[ix]][ni].level == sub_level+1)
		if (tree[node_it->group[ix]][ni].state == ONLINE) ++num;
    }
    if ((len = sprintf(&str[offset], "%u ", num)) < 0) perror("sprintf() error");
    offset += len;

    /* handle the sub_tree recursively */
    //num = node_it->group.size();
    for (ix = 0; ix != node_it->group.size(); ++ix)
    {
	offset = codeSubImage(node_it->group[ix], sub_level+1, str, offset);
    }	
    
    if ((len = sprintf(&str[offset], ")"))< 0) perror("sprintf() error ");
    offset += len;
    
    return offset;
}

/**********************************
class:	CGImage
method:	buildCGImage
**********************************/
int
CGImage::buildCGImage(char *str, CGNodeStatus stat)
{
    struct in_addr naddr;
    char s[20];
    int offset, i;
   
    pthread_mutex_lock(&lock);
    //tree.clear();
    setSubState(this->ip, this->level, OFFLINE);
    if (strlen(str) == 0) return 0;
    sscanf(str, "%u", &naddr);
    sprintf(s, "%s", inet_ntoa(naddr));
    this->father = s;
    for (offset = 0; str[offset] != ' '; ++offset);
    buildSubImage(father, str, &offset, stat);
    pthread_mutex_unlock(&lock);
}

/**********************************
class:	CGImage
method:	buildSubImage
return:	sub_root's IP
**********************************/
string
CGImage::buildSubImage(string sub_father, char *str, int *offset, CGNodeStatus stat)
{
    struct node p;
    char s[20];
    string cur_ip, child;
    struct in_addr naddr;
    int cur_level, num;
    vector<node>::size_type ni;
    vector<string>::size_type si;
    int len, i;
    
    while (1)
    {
    	switch (str[(*offset)])
	{
	    case ' ':
		++(*offset);
		break;

	    case '(':
		sscanf(&str[++(*offset)], "%u %u %u", &naddr, &cur_level, &num);
		for (i = 4; i > 0; ++(*offset))
		{
		    while (str[(*offset)] != ' ') ++(*offset);
		    --i;
		}
		sprintf(s, "%s", inet_ntoa(naddr));
		cur_ip = s;
		      
		for (ni = 0; ni != tree[cur_ip].size(); ++ni)
		    if (tree[cur_ip][ni].level == cur_level) break;
		if (ni < tree[cur_ip].size())		// old node with cur_level exist
		{
		    tree[cur_ip][ni].state = stat;
		    tree[cur_ip][ni].father = sub_father;
		    tree[cur_ip][ni].level = cur_level;
		    //tree[cur_ip][ni].group.clear();
		}
		else
		{
		    p.state = stat;
		    p.father = sub_father;
		    p.level = cur_level;
		    p.group.clear();
		    tree[cur_ip].push_back(p);
		}	    

		for (i = 1; i <= num; ++i)
		{
		    child = buildSubImage(cur_ip, str, offset, stat);
		    for (ni = 0; ni != tree[cur_ip].size(); ++ni)
			if (tree[cur_ip][ni].level == cur_level) break;
		    for (si = 0; si < tree[cur_ip][ni].group.size(); ++si)
			if (tree[cur_ip][ni].group[si] == child) break;
		    if (si >= tree[cur_ip][ni].group.size())
			tree[cur_ip][ni].group.push_back(child);	// add child into group
		}
		break;
		
	    case ')':
		++(*offset);
		return cur_ip;
		
	    default:
		return "";
	}	  
    }
}

/**********************************
class:	CGImage
method:	setSubState
set ONLINE/OFFLINE to every node in sub_tree
**********************************/
void
CGImage::setSubState(string sub_ip, int sub_level, CGNodeStatus stat)
{
    vector<node>::size_type ni;
    vector<string>::size_type si;

    if (!tree.count(sub_ip)) return;
    for (ni = 0; ni != tree[sub_ip].size(); ++ni)
	if (tree[sub_ip][ni].level == sub_level) break;
    if (ni >= tree[sub_ip].size()) return;
    tree[sub_ip][ni].state = stat;

    for (si = 0; si != tree[sub_ip][ni].group.size(); ++si)
    {
	setSubState(tree[sub_ip][ni].group[si], sub_level+1, stat);
    }
}

/**********************************
class:	CGImage
method:	setIpState
set ONLINE/OFFLINE to nodes of IP
**********************************/
void
CGImage::setIpState(string sub_ip, CGNodeStatus stat, int level_down)
{
    vector<node>::size_type ni;
    
    if (!tree.count(sub_ip)) return;
    for (ni = 0; ni != tree[sub_ip].size(); ++ni)
    {
	if (tree[sub_ip][ni].level < level_down)
	    tree[sub_ip][ni].state = stat;
    }
}

/**********************************
class:	CGImage
method:	indexCGNode, indexSubNode
param:	sub_ip, sub_level, index, *set, flag
	flag = 0 if same with ip
	flag = 1 if different from ip
return:	the number of index node
**********************************/
int
CGImage::indexCGNode(string cur_ip, int cur_level, string index, Set *set, int flag)
{
    pthread_mutex_lock(&lock);
    int count = indexSubNode(cur_ip, cur_level, index, set, flag);
    pthread_mutex_unlock(&lock);
    return count;
}

int
CGImage::indexSubNode(string sub_ip, int sub_level, string index, Set *set, int flag)
{
    vector<node>::size_type ni;
    vector<string>::size_type si;
    Position p;
    int count = 0;

    if (!tree.count(sub_ip))
    {
	printf("indexSubNode() %s not exist in tree_map\n", sub_ip.c_str());
	return 0;
    }
    
    for (ni = 0; ni != tree[sub_ip].size(); ++ni)
    {
	if (tree[sub_ip][ni].level == sub_level) break;
    }
    if (tree[sub_ip][ni].state != ONLINE) return 0;	// subtree offline
    
    if ((flag && sub_ip != index) || (!flag && sub_ip == index))
    {
	count = 1;
	p.ip = sub_ip;
	p.level = sub_level;
	set->push_back(p);
    }
    
    for (si = 0; si != tree[sub_ip][ni].group.size(); ++si)
    {
	count += indexSubNode(tree[sub_ip][ni].group[si], sub_level+1, index, set, flag); 
    }
    return count;
}

/**********************************
class:	CGImage
method:	indexIPNode
param:	index, *set
index nodes with IP in the whole cg_tree
**********************************/
int
CGImage::indexIPNode(string index, Set *set)
{
    vector<node>::size_type ni;
    Position p;
    string node;
    int num;

    pthread_mutex_lock(&lock);
    if (!tree.count(index))
    {
	printf("indexIPNode() %s not exist in tree_map\n", index.c_str());
	pthread_mutex_unlock(&lock);
	return -1;
    }
    p.ip = index;
    for (ni = 0; ni != tree[index].size(); ++ni)
    {
	if (tree[index][ni].state == ONLINE)
	{
	    p.level = tree[index][ni].level;
	    set->push_back(p);
	}
    }
    num = set->size();
    pthread_mutex_unlock(&lock);
    return num;
}

/**********************************
class:	CGImage
method:	indexChldNode
return:	number of children
**********************************/
int
CGImage::indexChldNode(string cur_ip, int cur_level, Set *set)
{
    vector<node>::size_type ni, mi;
    vector<string>::size_type si;
    Position p;
    string child;
    int num;
  
    pthread_mutex_lock(&lock);
    if (!tree.count(cur_ip))
    {
	printf("indexChldNode() %s not exist in tree_map\n", cur_ip.c_str());
	pthread_mutex_unlock(&lock);
	return -1;
    }
    for (ni = 0; ni != tree[cur_ip].size(); ++ni)
    {
	if (tree[cur_ip][ni].level == cur_level) break;
    }
    p.level = cur_level + 1;
    for (si = 0; si != tree[cur_ip][ni].group.size(); ++si)
    {
	child = tree[cur_ip][ni].group[si];
	for (mi = 0; mi != tree[child].size(); ++mi)
	    if (tree[child][mi].level == cur_level+1) break;
	if (tree[child][mi].state == ONLINE)
	{
	    p.ip = child;
	    set->push_back(p);
	}
    }
    num = set->size();
    pthread_mutex_unlock(&lock);
    return num;
}

/**********************************
class:	CGImage
method:	getNodeState
check whether a node is ONLINE or OFFLINE
**********************************/
int
CGImage::getNodeState(string node_ip)
{
    vector<node>::size_type ni;
    int state;

    pthread_mutex_lock(&lock);
    for (ni = 0; ni != tree[node_ip].size(); ++ni)
	if (tree[node_ip][ni].level == this->depth-1) break;
    state = tree[node_ip][ni].state;
    pthread_mutex_unlock(&lock);
    return state;
}

/**********************************
class:	CGImage
method:	adjust
param:	sub_ip
	sub_state - this node's state
return:	the newly node's ip
when a node just add into or leave from
tree, update the image according to node's priority
then the cgtree reconstruct level by level
**********************************/
string
CGImage::adjustImage(string sub_ip, CGNodeStatus sub_state, int *end_level, string *off_ip)
{
    vector<node>::iterator cur_it, old_it;
    vector<node>::size_type ni;
    vector<string>::size_type ix;
    string cur_ip, newfather, oldfather;
    int maxi, cur_level;
    struct node p;

    pthread_mutex_lock(&lock);
    for (cur_it = tree[sub_ip].begin(); cur_it != tree[sub_ip].end(); ++cur_it)
    {
	if (sub_state == OFFLINE) cur_it->state = sub_state;
	if (cur_it->level == this->depth-1) old_it = cur_it;	// get the leaf_node
    }

    cur_it = old_it;
    cur_it->state = sub_state;
    cur_ip = sub_ip;
    cur_level = cur_it->level;
    *off_ip = "";
  
    /* loop in every level, bottom up */
    while (cur_level > this->level)
    {
	/* renew the father */
	for (old_it = tree[cur_it->father].begin(); old_it != tree[cur_it->father].end(); ++old_it)
	    if (old_it->level == cur_level-1) break;		// old_it point to the old father
	if (old_it == tree[cur_it->father].end())
	{
#ifdef DEBUG
	    printf("%s(%d) can not find father\n", cur_ip.c_str(), cur_level);
#endif
	    break;
	}

#ifdef DEBUG
	/* print cur_it node and its father,children */
	printf("*** Level Image ***\n");
	printf("CurNode: %s(%d)[%d]  ", cur_ip.c_str(), cur_level, cur_it->state);
	printf("Father: %s(%d)[%d]\n", cur_it->father.c_str(), cur_level-1, old_it->state);
	printf("Father_Group: %d ", old_it->group.size());
	for (ix = 0; ix < old_it->group.size(); ++ix)
	{
	    for (ni = 0; ni != tree[old_it->group[ix]].size(); ++ni)
		if (tree[old_it->group[ix]][ni].level == cur_level) break;
	    printf("%s(%d)", old_it->group[ix].c_str(), cur_level, tree[old_it->group[ix]][ni].state);
	    if (ni < tree[old_it->group[ix]].size())
		printf("[%d] ", tree[old_it->group[ix]][ni].state);
	    else printf("[%d] ", -1);
	}
	printf("\n");
#endif

	/* cur_ip just leave from tree */
	if (cur_it->state == OFFLINE)
	{
	    *off_ip = cur_ip;
	    
	    if (cur_ip == cur_it->father)
	    {
	    	for (maxi = -1, ix = 0; ix < old_it->group.size(); ++ix)
	    	{
		    /* find a online child node with the highest priority */
		    if (old_it->group[ix] == cur_ip) continue;
		    for (ni = 0; ni != tree[old_it->group[ix]].size(); ++ni)
			if (tree[old_it->group[ix]][ni].level == cur_level) break;
		    if (ni < tree[old_it->group[ix]].size() && tree[old_it->group[ix]][ni].state == ONLINE)	// node online
		    {
			if (maxi == -1) maxi = ix;
			else
			{
			    if (table[old_it->group[ix]] < table[old_it->group[maxi]])
				maxi = ix;	// node with higher priority
			}
		    }
		}
		if (maxi > -1)	// find a online child to be new group leader
		{
#ifdef DEBUG
		    printf("@ find a online chid to be new group leader\n");
#endif
		    /* renew every child's father_value */
		    newfather = old_it->group[maxi];
		    for (ix = 0; ix < old_it->group.size(); ++ix)
		    {
			for (ni = 0; ni != tree[old_it->group[ix]].size(); ++ni)
			    if (tree[old_it->group[ix]][ni].level == cur_level) break;
			if (ni < tree[old_it->group[ix]].size())
			    tree[old_it->group[ix]][ni].father = newfather;
		    }
		
#ifdef DEUBG
		    printf("672 ");
#endif
		    /* renew father's group_value*/
		    if (cur_level >= 2)
		    {
		    	for (ni = 0; ni != tree[old_it->father].size(); ++ni)
			    if (tree[old_it->father][ni].level == cur_level-2) break;
			for (ix = 0; ix < tree[old_it->father][ni].group.size(); ++ix)
			    if (tree[old_it->father][ni].group[ix] == newfather) break;
			if (ix >= tree[old_it->father][ni].group.size())
			    tree[old_it->father][ni].group.push_back(newfather);
		    }
		   
#ifdef DEBUG
		    printf("686 ");
#endif
		    /* add the father node with cur_ip and cur_level-1 */
		    for (ni = 0; ni != tree[newfather].size(); ++ni)
			if (tree[newfather][ni].level == cur_level-1) break;
		    if (ni < tree[newfather].size())	// old node with cur_level-1 exist
		    {
			tree[newfather][ni].state = ONLINE;
			tree[newfather][ni].father = old_it->father;
			tree[newfather][ni].level = old_it->level;
			tree[newfather][ni].group = old_it->group;
		    }
		    else				// create a new node with cur_level-1
		    {
			p.state = ONLINE;
		 	p.father = old_it->father;
			p.level = old_it->level;
			p.group = old_it->group;
			tree[newfather].push_back(p);
		    }
		    
		    old_it->state = OFFLINE;
		    // old_it->group.clear();

#ifdef DEBUG
		    printf("711\n");
#endif
		    /* update the while_loop iterator */
		    cur_ip = newfather;
		    for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
			if (cur_it->level == cur_level-1) break;
		    --cur_level;
		}
		else	// not other online node
		{
#ifdef DEBUG
		    printf("@ not other online node\n");
#endif
		    old_it->state = OFFLINE;

		    cur_ip = cur_ip;
		    for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
			if (cur_it->level == cur_level-1) break;
		    --cur_level;
		}
	    }
	    else	// not group_leader's error, cur_ip != cur_it->father
	    {
#ifdef DEBUG
		printf("@ only child OFFLINE\n");
#endif
		//cur_ip = cur_it->father;
		//for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
		//    if (cur_it->level == cur_level-1) break;
		//--cur_level;
		cur_ip = "";
		break;
	    }
	}

	/* cur_ip just add into tree */
	else if (cur_it->state == ONLINE)
	{
	    if (cur_ip == cur_it->father)	// cur_ip(cur_level) is the previous group leader
	    {
#ifdef DEBUG
		printf("@ state ONLINE, level up\n");
#endif
		/* update the while_loop iterator */
		cur_ip = cur_ip;
		for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
		    if (cur_it->level == cur_level-1) break;
		cur_it->state = ONLINE;
		--cur_level;
	    }
	    else	// cur_ip != cur_it->father
	    {
	    	if (old_it->state == OFFLINE || table[cur_ip] < table[cur_it->father])	// current node will be a new father
		{
#ifdef DEBUG
		    printf("@ cur_ip replace old_father\n");
#endif
		    /* renew every child's father_value */
		    oldfather = cur_it->father;
		    newfather = cur_ip;
		    for (ix = 0; ix < old_it->group.size(); ++ix)
		    {
			for (ni = 0; ni != tree[old_it->group[ix]].size(); ++ni)
			    if (tree[old_it->group[ix]][ni].level == cur_level) break;
			if (ni < tree[old_it->group[ix]].size())
			    tree[old_it->group[ix]][ni].father = newfather;
		    }

#ifdef DEBUG
		    printf("780 ");
#endif
		    /* renew father's group_value*/
		    if (cur_level >= 2)
		    {
		    	for (ni = 0; ni != tree[old_it->father].size(); ++ni)
			    if (tree[old_it->father][ni].level == cur_level-2) break;
			for (ix = 0; ix < tree[old_it->father][ni].group.size(); ++ix)
			    if (tree[old_it->father][ni].group[ix] == newfather) break;
			if (ix >= tree[old_it->father][ni].group.size())
			    tree[old_it->father][ni].group.push_back(newfather);
		    }

#ifdef DEBUG
		    printf("794 ");
#endif
		    /* add the father node with cur_ip and cur_level-1 */
		    for (ni = 0; ni != tree[newfather].size(); ++ni)
			if (tree[newfather][ni].level == cur_level-1) break;
		    if (ni < tree[newfather].size())	// old node with cur_level-1 exist
		    {
			tree[newfather][ni].state = ONLINE;
			tree[newfather][ni].father = old_it->father;
			tree[newfather][ni].level = old_it->level;
			tree[newfather][ni].group = old_it->group;
		    }
		    else				// create a new node with cur_level-1
		    {
			struct node p;
			p.state = ONLINE;
			p.father = old_it->father;
			p.level = old_it->level;
			p.group = old_it->group;
			tree[newfather].push_back(p);
		    }

#ifdef DEBUG
		    printf("817 ");
#endif
		    /* delete the old father node */
		    //old_it->group.clear();
		    old_it->state = OFFLINE;
		    if (table[newfather] < table[oldfather])
			tree[oldfather].erase(old_it);
		    *off_ip = oldfather;

#ifdef DEBUG
		    printf("827\n");
#endif
		    /* update the while_loop iterator */
		    cur_ip = newfather;
		    for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
			if (cur_it->level == cur_level-1) break;
		    --cur_level;
		}
		else	// subtree adjust complete
		{
#ifdef DEBUG
		    printf("@ subtree adjust complete\n");
#endif
		    /* renew father's group_value*/
		    if (cur_level >= 1)
		    {
		    	for (ni = 0; ni != tree[cur_it->father].size(); ++ni)
			    if (tree[cur_it->father][ni].level == cur_level-1) break;
			for (ix = 0; ix < tree[cur_it->father][ni].group.size(); ++ix)
			    if (tree[cur_it->father][ni].group[ix] == cur_ip) break;
			if (ix >= tree[cur_it->father][ni].group.size())
			    tree[cur_it->father][ni].group.push_back(cur_ip);
		    }

		    //*off_ip = "";
		    
		    //cur_ip = old_it->father;
		    //for (cur_it = tree[cur_ip].begin(); cur_it != tree[cur_ip].end(); ++cur_it)
		    //	if (cur_it->level == cur_level-1) break;
		    //--cur_level;
		    
		    break;	// stay in old subtree_structure
		}
	    }
	}
    }
    
    pthread_mutex_unlock(&lock);
    *end_level = cur_level;
#ifdef DEBUG
    printf("image_adjust return ip:%s(%d), off_ip:%s\n", cur_ip.c_str(), cur_level, (*off_ip).c_str());
#endif
    return cur_ip;
}

/**********************************
class:	CGImage
method:	updateImage
**********************************/
int
CGImage::updateImage(string child, int sub_level, char *str)
{
    Set set;
    struct in_addr naddr;
    char s[20];
    string sub_father;
    vector<node>::size_type ni;
    vector<string>::size_type si;
    int offset;

    pthread_mutex_lock(&lock);
    setSubState(child, sub_level, OFFLINE);
    sscanf(str, "%u", &naddr);
    sprintf(s, "%s", inet_ntoa(naddr));
    sub_father = s;
   
    /* add child into its father's group */
    for (ni = 0; ni != tree[sub_father].size(); ++ni)
	if (tree[sub_father][ni].level == sub_level-1) break;
    for (si = 0; si != tree[sub_father][ni].group.size(); ++si)
	if (tree[sub_father][ni].group[si] == child) break;
    if (si >= tree[sub_father][ni].group.size())
	tree[sub_father][ni].group.push_back(child);
    
    for (offset = 0; str[offset] != ' '; ++offset);
    buildSubImage(sub_father, str, &offset, ONLINE);

    for (ni = 0; ni != tree[child].size(); ++ni)
	if (tree[child][ni].level == sub_level) break;
    for (si = 0; si != tree[child][ni].group.size(); ++si)
    {
	if (tree[child][ni].group[si] != child)
	    setIpState(tree[child][ni].group[si], OFFLINE, sub_level+1);
    }
    pthread_mutex_unlock(&lock);
}

/**********************************
class:	CGImage
method: getFather
return:	node's father
**********************************/
/*string
CGImage::getFather(string )
{
    vector<node>::iterator node_it;

    node_it = tree[this->ip].begin();
    while (node_it != tree[this->ip].end())
    {
	if (node_it->level == this->level) break;
	++node_it;
    }
    return node_it->father;
}*/

